package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/5/8 20:09
 */
public class 最大正方形 {

    public static void main(String[] args) {
        char[][] matrix = {{'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '0', '1', '1', '0'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}};
        System.out.println(maximalSquare(matrix));
    }

    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if(m == 0){
            return 0;
        }
        int n = matrix[0].length;
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    int size = m - i > n - j ? n - j : m - i;
                    for (int k = 1; k <= size; k++) {
                        if (isSquare(matrix, i, j, k)) {
                            max = Math.max(k * k, max);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        return max;
    }

    private static boolean isSquare(char[][] matrix, int i, int j, int k) {
        for (int m = i; m < i + k; m++) {
            for (int n = j; n < j + k; n++) {
                if (matrix[m][n] == '0') {
                    return false;
                }
            }
        }
        return true;
    }
}
